正则表达式匹配

动态规划：时间复杂度低
时间复杂度：O(mn) 空间复杂度：O(mn)

class Solution:
    def match(self , s: str, pattern: str) -> bool:
        n = len(s)
        m = len(pattern)
        dp = [[False]*(m+2) for i in range(n+1)]
        dp[0][0] = True
        # str为空的情况
        for j in range(2, m+1):
            if pattern[j-1] == '*':
                dp[0][j] = dp[0][j-2]
        for i in range(1, n+1):
            for j in range(m+1):
                if pattern[j-1] != '*' and (pattern[j-1] == '.' or pattern[j-1] == s[i-1]):
                    dp[i][j] = dp[i-1][j-1]
                elif j > 1 and pattern[j-1] == '*':
                    if pattern[j-2] == '.' or pattern[j-2] == s[i-1]:
                        dp[i][j] = dp[i-1][j] or dp[i][j-2]
                    else:
                        dp[i][j] = dp[i][j-2]
        return dp[n][m]

class Solution:
    # 递归回溯方法
    def match(self , str: str, pattern: str) -> bool:
        # 终止条件
        if not pattern:
            return not str
        # 首项匹配条件
        first_match = str and pattern[0] in {str[0], '.'}

        # 带*的情况
        if len(pattern) >= 2 and pattern[1] == '*':
            # 第一种情况p中*的前一个元素在s中不出现，则截掉p中的前两个元素，s不变。如：s='bc',p='a*bc',将p的首部2个元素截去，得到'bc',继续比较
            # 第二种情况如果*的前一个元素在s中出现，则比较首项元素(first_match)是否相等，在把s截掉首项，p不变。
            # 如：s='aabc',p='a*bc',那么比较首项元素是否相等，截去s首元素得到s='abc'继续与p='a*bc'比较
            # 当然会出现这种情况：s='abc',p='a*abc;按1来说，p截去首两个元素,s='abc',p='abc'匹配成功；按2来说，s='bc',p='a*abc'匹配失败，所以这两种情况只要走通一种情况即可
            return (self.match(str, pattern[2:])) or (first_match and self.match(str[1:], pattern))
        else:
            # 一般情况：即不带*的情况
            return first_match and self.match(str[1:], pattern[1:])

import re
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        cre = re.compile(pattern)

        return True if cre.fullmatch(str) else False

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
# import functools
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        m , n = len(str) , len(pattern)
        cache = {}
#         @functools.lru_cache(None)
        def dfs(i , j):
            if (i,j) in cache:
                return cache[(i,j)]
            if j == n:
                return i == m 
            if j + 1 < n and pattern[j+1] == '*':
                if i < m and (str[i] == pattern[j]&nbs***bsp;pattern[j] == '.'):
                    cache[(i,j)] =  dfs(i+1, j)&nbs***bsp;dfs(i, j + 2) # * 不匹配当前的额前一个
                    return cache[(i,j)]
                else:
                    cache[(i,j)] = dfs(i,j + 2)
                    return cache[(i,j)] 
            else:
                cache[(i,j)] = i < m and (str[i] == pattern[j]&nbs***bsp;pattern[j] == '.') and dfs(i+1,j+1)
                return cache[(i,j)]
        return dfs(0,0)              

class Solution:
    def match(self, str: str, pattern: str) -> bool:
        m = len(str)
        n = len(pattern)
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
        dp[m][n] = True
        for i in range(m, -1, -1):
            for j in range(n - 1, -1, -1):
                isMatch =  i < len(str) and (str[i] == pattern[j]&nbs***bsp;pattern[j] == ".")
                if j + 1 < len(pattern) and pattern[j + 1] == "*":
                    dp[i][j] = (isMatch and dp[i + 1][j])&nbs***bsp;dp[i][j + 2]
                else:
                    dp[i][j] = (isMatch and dp[i + 1][j + 1])
        return dp[0][0]

class Solution:
    def match(self, str, pattern):
        # 字符串和表达式全为空才算正确
        # 如果字符串不为空，但是表达式为空那么此时一定错误
        # 如果字符串为空，表达式不为空则不一定，如''和'.*'
        if not pattern:
            return not str
        if len(pattern) > 1 and pattern[1] == '*':
            if str and (pattern[0] == '.'&nbs***bsp;pattern[0] == str[0]):
                # 带*可以匹配0-n次
                return self.match(str, pattern[2:])&nbs***bsp;self.match(str[1:], pattern)
            else:
                return self.match(str, pattern[2:])
        else:
            if str and (pattern[0] == '.'&nbs***bsp;str[0] == pattern[0]):
                return self.match(str[1:], pattern[1:])
            else:
                return False
        return False

class Solution:
    def match(self , str , pattern ):
        # write code here
        if str == "" and pattern == "":
            return True
        if pattern == "":
            return False
        if str == "":
            return self.f(pattern)
        return self.process(str, pattern, 0, 0)

    
    def f(self, s):
        i = 1
        while i < len(s):
            if s[i] != "*":
                return False
            i += 2
        if i == len(s):
            return False
        if i == len(s) + 1:
            return True


    def process(self, str, pattern, i, j):
        if i == len(str) and j == len(pattern):
            return True
        if i == len(str) and j < len(pattern):
            return self.f(pattern[j:])
        if i < len(str) and j == len(pattern):
            return False
        if j + 1 < len(pattern) and pattern[j+1] == "*":
            if str[i] == pattern[j]&nbs***bsp;pattern[j] == ".":
                return self.process(str, pattern, i, j+2)&nbs***bsp;self.process(str, pattern, i+1, j+2)&nbs***bsp;self.process(str, pattern, i+1, j)
            else:
                return self.process(str, pattern, i, j+2)
        if str[i] == pattern[j]&nbs***bsp;pattern[j] == ".":
            return self.process(str, pattern, i+1, j+1)
        return False

class Solution:
    def match(self , str , pattern ):
        # write code here
        m = len(str)
        n = len(pattern)

        # dp[i][j] 表示str前i-1位与pattern前j-1位是否匹配。i = 0 或j = 0表示空字符串
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = True
        # 当str为空字符串时，需要考虑*，当pattern为空字符串时，除dp[0][0]外全部为False
        for i in range(1, n + 1):
            y = i - 1
            if pattern[y] == "*":
                dp[0][i] = dp[0][i - 2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                x = i - 1
                y = j - 1
                if pattern[y] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                elif pattern[y] == '*':
                    if str[x] == pattern[y - 1]&nbs***bsp;pattern[y - 1] == '.':
                        dp[i][j] = dp[i - 1][j]&nbs***bsp;dp[i - 1][j - 2]
                    else:
                        dp[i][j] = dp[i][j - 2]
                else:
                    if str[x] == pattern[y]:
                        dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]

class Solution:
    def match(self , str , pattern ):
        # write code here
        # 定义初始条件
        if len(pattern)==0:
            return len(str)==0
        m = (len(str)>0) and (pattern[0]==str[0]&nbs***bsp;pattern[0]=='.')
        if len(pattern)>1 and pattern[1]=='*':
            return self.match(str,pattern[2:])&nbs***bsp;(m and self.match(str[1:],pattern))
        else:
            return m and self.match(str[1:], pattern[1:])